//衣橱整理
/*家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。
1 <= n, m <= 100
0 <= cnt <= 20
*/
class Solution {
    bool vis[101][101] = {0};
    int count = 0;
    // int sum_max = 0;
    int m, n;
    int dx[2] = {0, 1};
    int dy[2] = {1, 0};

public:
    bool x_y_sum(int& cnt, int x, int y) {
        int sum = 0;
        while (x) {
            sum += (x % 10);
            x /= 10;
        }
        while (y) {
            sum += (y % 10);
            y /= 10;
        }
        if (sum > cnt)
            return false;
        return true;
    }
    int wardrobeFinishing(int _m, int _n, int cnt) {
        m = _m;
        n = _n;
        int x = 0;
        int y = 0;
        if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&
            x_y_sum(cnt, x, y))
            dfs(cnt, x, y);
            return count;
    }
    void dfs(int& cnt, int i, int j) {
        vis[i][j] = true;
        count++;
        for (int k = 0; k < 2; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&
                x_y_sum(cnt, x, y))
                dfs(cnt, x, y);
        }
    }
};


//斐波那契数
/*斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。
0 <= n <= 100
*/
class Solution {
    vector<int> ret;

public:
    int fib(int n) {
        ret = vector<int>(n + 1, -1);
        dfs(n);
        return ret[n]%1000000007;
    }
    int dfs(int n) {
        if (ret[n] != -1)
            return ret[n];
        if (n == 0 || n == 1) {
            ret[n] = n;
            return n;
        }
        ret[n] =
            dfs(n - 1) % (1000000007) + dfs(n - 2) % (1000000007);
        return ret[n]%1000000007;
    }
};
